SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Data-flow analysis</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Data-flow analysis</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about static program analysis. For dynamic program analysis, see <a href="Dynamic_program_analysis#Dynamic_data-flow_analysis" title="Dynamic program analysis">Dynamic program analysis § Dynamic data-flow analysis</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar sidebar-collapse nomobile"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Software_development" title="Software development">Software development</a></th></tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Core activities</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Data_modeling" title="Data modeling">Data modeling</a></li>

<li><a href="Software_development_process" title="Software development process">Processes</a></li>

<li><a href="Requirements_analysis" title="Requirements analysis">Requirements</a></li>

<li><a href="Software_design" title="Software design">Design</a></li>

<li><a href="Software_construction" title="Software construction">Construction</a></li>

<li><a href="Software_engineering" title="Software engineering">Engineering</a></li>

<li><a href="Software_testing" title="Software testing">Testing</a></li>

<li><a href="Debugging" title="Debugging">Debugging</a></li>

<li><a href="Software_deployment" title="Software deployment">Deployment</a></li>

<li><a href="Software_maintenance" title="Software maintenance">Maintenance</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Paradigms and models</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Agile_software_development" title="Agile software development">Agile</a></li>

<li><a href="Cleanroom_software_engineering" title="Cleanroom software engineering">Cleanroom</a></li>

<li><a href="Incremental_build_model" title="Incremental build model">Incremental</a></li>

<li><a href="Software_prototyping" title="Software prototyping">Prototyping</a></li>

<li><a href="Spiral_model" title="Spiral model">Spiral</a></li>

<li><a href="V-model_(software_development)" title="V-model (software development)">V model</a></li>

<li><a href="Waterfall_model" title="Waterfall model">Waterfall</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><a href="Software_development_methodology" class="mw-redirect" title="Software development methodology">Methodologies</a> and frameworks</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="DevOps" title="DevOps">DevOps</a></li>

<li><a href="Kanban_(development)" title="Kanban (development)">Kanban</a></li>

<li><a href="Scrum_(software_development)" title="Scrum (software development)">Scrum</a></li>

<li><a href="SEMAT" title="SEMAT">SEMAT</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Supporting disciplines</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Software_configuration_management" title="Software configuration management">Configuration management</a></li>

<li><a href="Deployment_management#Computer_science" title="Deployment management">Deployment management</a></li>

<li><a href="Software_documentation" title="Software documentation">Documentation</a></li>

<li><a href="Software_project_management" title="Software project management">Project management</a></li>

<li><a href="Software_quality_assurance" title="Software quality assurance">Quality assurance</a></li>

<li><a href="User_experience" title="User experience">User experience</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Practices</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="Stand-up_meeting" title="Stand-up meeting">Stand-up</a></li>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)"><a href="Programming_tool" title="Programming tool">Tools</a></div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Build_automation" title="Build automation">Build automation</a></li>

<li><a href="Compiler" title="Compiler">Compiler</a></li>

<li><a href="Debugger" title="Debugger">Debugger</a></li>

<li><a href="Graphical_user_interface_builder" title="Graphical user interface builder">GUI builder</a></li>

<li><a href="Infrastructure_as_code" title="Infrastructure as code">Infrastructure as code</a></li>

<li><a href="Profiling_(computer_programming)" title="Profiling (computer programming)">Profiler</a></li>

<li><a href="Application-release_automation" title="Application-release automation">Release automation</a></li>

<li><a href="UML_tool" title="UML tool">UML Modeling</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Standards and bodies of knowledge</div><div class="sidebar-list-content mw-collapsible-content hlist">

<li><a href="IEEE_Standards_Association" title="IEEE Standards Association">IEEE standards</a></li>

<li><a href="ISO/IEC_JTC_1/SC_7" title="ISO/IEC JTC 1/SC 7">ISO/IEC standards</a></li>

<li><a href="Project_Management_Body_of_Knowledge" title="Project Management Body of Knowledge">PMBOK</a></li>

<li><a href="Software_Engineering_Body_of_Knowledge" title="Software Engineering Body of Knowledge">SWEBOK</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Glossaries</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Glossary_of_artificial_intelligence" title="Glossary of artificial intelligence">Artificial intelligence</a></li>

<li><a href="Glossary_of_computer_science" title="Glossary of computer science">Computer science</a></li>

<li><a href="Glossary_of_electrical_and_electronics_engineering" title="Glossary of electrical and electronics engineering">Electrical and electronics engineering</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-content">

<div class="sidebar-list mw-collapsible mw-collapsed"><div class="sidebar-list-title" style="color: var(--color-base)">Outlines</div><div class="sidebar-list-content mw-collapsible-content hlist">

<ul><li><a href="Outline_of_software_development" title="Outline of software development">Outline of software development</a></li></ul></div></div></td>

</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p><b>Data-flow analysis</b> is a technique for gathering information about the possible set of values calculated at various points in a <a href="Computer_program" title="Computer program">computer program</a>. It forms the foundation for a wide variety of compiler optimizations and program verification techniques. A program's <a href="Control-flow_graph" title="Control-flow graph">control-flow graph</a> (CFG) is used to determine those parts of a program to which a particular value assigned to a variable might propagate. The information gathered is often used by <a href="Compiler" title="Compiler">compilers</a> when <a href="Optimizing_compiler" title="Optimizing compiler">optimizing</a> a program. A canonical example of a data-flow analysis is <a href="Reaching_definitions" class="mw-redirect" title="Reaching definitions">reaching definitions</a>. Other commonly used data-flow analyses include live variable analysis, available expressions, constant propagation, and very busy expressions, each serving a distinct purpose in compiler optimization passes.

</p><p>A simple way to perform data-flow analysis of programs is to set up data-flow equations for each <a href="Node_(computer_science)" title="Node (computer science)">node</a> of the control-flow graph and solve them by repeatedly calculating the output from the input locally at each node until the whole system stabilizes, i.e., it reaches a <a href="Fixpoint" class="mw-redirect" title="Fixpoint">fixpoint</a>. The efficiency and precision of this process are significantly influenced by the design of the data-flow framework, including the direction of analysis (forward or backward), the domain of values, and the join operation used to merge information from multiple control paths.This general approach, also known as <i>Kildall's method</i>, was developed by <a href="Gary_Kildall" title="Gary Kildall">Gary Kildall</a> while teaching at the <a href="Naval_Postgraduate_School" title="Naval Postgraduate School">Naval Postgraduate School</a>.<sup id="cite_ref-Kildall_1972_Optimization_1-0" class="reference"><a href="#cite_note-Kildall_1972_Optimization-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Kildall_1973_Optimization_2-0" class="reference"><a href="#cite_note-Kildall_1973_Optimization-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Cortesi_1999_3-0" class="reference"><a href="#cite_note-Cortesi_1999-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Laws_2014_IEEE_4-0" class="reference"><a href="#cite_note-Laws_2014_IEEE-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Kildall19732_5-0" class="reference"><a href="#cite_note-Kildall19732-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Aho2006_6-0" class="reference"><a href="#cite_note-Aho2006-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Basic_principles">Basic principles</h2></div>

<p>Data-flow analysis is the process of collecting information about the way the variables are defined and used in the program. It attempts to obtain particular information at each point in a procedure. Usually, it is enough to obtain this information at the boundaries of <a href="Basic_block" title="Basic block">basic blocks</a>, since from that it is easy to compute the information at points in the basic block. In forward flow analysis, the exit state of a block is a function of the block's entry state. This function is the composition of the effects of the statements in the block. The entry state of a block is a function of the exit states of its predecessors. This yields a set of data-flow equations:

</p><p>For each block b:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle out_{b}=trans_{b}(in_{b})}</annotation>

</semantics>

</math></span><img src="./ce421ec7ffdb068452ae712ada535e1117604a9d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.818ex; height:2.843ex;" alt="{\displaystyle out_{b}=trans_{b}(in_{b})}" loading="lazy"></span></dd>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}</annotation>

</semantics>

</math></span><img src="./2491805aae170e52d559f1a140f670c2e5ae17f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:22.763ex; height:3.009ex;" alt="{\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle trans_{b}}</annotation>

</semantics>

</math></span><img src="./afaf00711186920e4880c49d8095f223b91bb43d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.541ex; height:2.343ex;" alt="{\displaystyle trans_{b}}" loading="lazy"></span> is the <b>transfer function</b> of the block <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>. It works on the entry state <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle in_{b}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle in_{b}}</annotation>

</semantics>

</math></span><img src="./4c4f6c307ecb1ffc5b3069ea36b4b97069d455df.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.135ex; height:2.509ex;" alt="{\displaystyle in_{b}}" loading="lazy"></span>, yielding the exit state <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle out_{b}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle out_{b}}</annotation>

</semantics>

</math></span><img src="./300f16a13da373f438aa18367632a14c513d704d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.235ex; height:2.343ex;" alt="{\displaystyle out_{b}}" loading="lazy"></span>. The <a href="Join_(mathematics)" class="mw-redirect" title="Join (mathematics)">join operation</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle join}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle join}</annotation>

</semantics>

</math></span><img src="./4e7fa39be3c631b104310334404ce69b20dd5925.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:4.31ex; height:2.509ex;" alt="{\displaystyle join}" loading="lazy"></span> combines the exit states of the predecessors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in pred_{b}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in pred_{b}}</annotation>

</semantics>

</math></span><img src="./f4629c9ca7543b84f875bf8fa17ae79912f2f39c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:9.548ex; height:2.509ex;" alt="{\displaystyle p\in pred_{b}}" loading="lazy"></span> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span>, yielding the entry state of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</p><p>After solving this set of equations, the entry and/or exit states of the blocks can be used to derive properties of the program at the block boundaries. The transfer function of each statement separately can be applied to get information at a point inside a basic block.

</p><p>Each particular type of data-flow analysis has its own specific transfer function and join operation. Some data-flow problems require backward flow analysis. This follows the same plan, except that the transfer function is applied to the exit state yielding the entry state, and the join operation works on the entry states of the successors to yield the exit state.

</p><p>The <a href="Entry_point" title="Entry point">entry point</a> (in forward flow) plays an important role: Since it has no predecessors, its entry state is well defined at the start of the analysis. For instance, the set of local variables with known values is empty. If the control-flow graph does not contain cycles (there were no explicit or implicit <a href="Control_flow#Loops" title="Control flow">loops</a> in the procedure) solving the equations is straightforward. The control-flow graph can then be <a href="Topological_sort" class="mw-redirect" title="Topological sort">topologically sorted</a>; running in the order of this sort, the entry states can be computed at the start of each block, since all predecessors of that block have already been processed, so their exit states are available. If the control-flow graph does contain cycles, a more advanced algorithm is required.

</p>

<div class="mw-heading mw-heading2"><h2 id="An_iterative_algorithm">An iterative algorithm</h2></div>

<p>The most common way of solving the data-flow equations is by using an iterative algorithm. It starts with an approximation of the in-state of each block. The out-states are then computed by applying the transfer functions on the in-states. From these, the in-states are updated by applying the join operations. The latter two steps are repeated until we reach the so-called <b>fixpoint</b>: the situation in which the in-states (and the out-states in consequence) do not change.

</p><p>A basic algorithm for solving data-flow equations is the <b>round-robin iterative algorithm</b>:

</p>

<dl><dd><i>initialize node i</i></dd></dl></dd>

<dd>while (<i>sets are still changing</i>)

<dl><dd><i>recompute sets at node i</i></dd></dl></dd></dl></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Convergence">Convergence</h3></div>

<p>To be usable, the iterative approach should actually reach a fixpoint. This can be guaranteed

by imposing constraints on the combination of the value domain of the states, the transfer functions and the join operation.

</p><p>The value domain should be a <a href="Partial_order" class="mw-redirect" title="Partial order">partial order</a> with <b>finite height</b> (i.e., there are no infinite ascending chains <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math></span><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"></span> < <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation>

</semantics>

</math></span><img src="./d7af1b928f06e4c7e3e8ebfd60704656719bd766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}" loading="lazy"></span> < ...). The combination of the transfer function and the join operation should be <a href="Monotonic" class="mw-redirect" title="Monotonic">monotonic</a> with respect to this partial order. Monotonicity ensures that on each iteration the value will either stay the same or will grow larger, while finite height ensures that it cannot grow indefinitely. Thus we will ultimately reach a situation where T(x) = x for all x, which is the fixpoint.

</p>

<div class="mw-heading mw-heading3"><h3 id="The_work_list_approach">The work list approach</h3></div>

<p>It is easy to improve on the algorithm above by noticing that the in-state of a block will not change if the out-states of its predecessors don't change. Therefore, we introduce a <b>work list</b>: a list of blocks that still need to be processed. Whenever the out-state of a block changes, we add its successors to the work list. In each iteration, a block is removed from the work list. Its out-state is computed. If the out-state changed, the block's successors are added to the work list. For efficiency, a block should not be in the work list more than once.

</p><p>The algorithm is started by putting information-generating blocks in the work list. It terminates when the

work list is empty.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ordering">Ordering</h3></div>

<p>The efficiency of iteratively solving data-flow equations is influenced by the order at which local nodes are visited.<sup id="cite_ref-Cooper_2004_9-0" class="reference"><a href="#cite_note-Cooper_2004-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> Furthermore, it depends on whether the data-flow equations are used for forward or backward data-flow analysis over the CFG. Intuitively, in a forward flow problem, it would be fastest if all predecessors of a block have been processed before the block itself, since then the iteration will use the latest information. In the absence of loops it is possible to order the blocks in such a way that the correct out-states are computed by processing each block only once.

</p><p>In the following, a few iteration orders for solving data-flow equations are discussed

(a related concept to iteration order of a <a href="Control-flow_graph" title="Control-flow graph">CFG</a> is <a href="Tree_traversal" title="Tree traversal">tree traversal</a> of a

<a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>).

</p>

<ul><li><b>Random order</b> - This iteration order is not aware whether the data-flow equations solve a forward or backward data-flow problem. Therefore, the performance is relatively poor compared to specialized iteration orders.</li>

<li><b><a href="Postorder" class="mw-redirect" title="Postorder">Postorder</a></b> - This is a typical iteration order for backward data-flow problems. In <i>postorder iteration</i>, a node is visited after all its successor nodes have been visited. Typically, the <i>postorder iteration</i> is implemented with the <b>depth-first</b> strategy.</li>

<li><b><a href="Depth-first_search#Vertex_orderings" title="Depth-first search">Reverse postorder</a></b> - This is a typical iteration order for forward data-flow problems. In <b>reverse-postorder iteration</b>, a node is visited before any of its successor nodes has been visited, except when the successor is reached by a back edge. (Note that reverse postorder is not the same as <a href="Depth-first_search#Vertex_orderings" title="Depth-first search">preorder</a>.)</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Initialization">Initialization</h3></div>

<p>The initial value of the in-states is important to obtain correct and accurate results.

If the results are used for compiler optimizations, they should provide <b>conservative</b> information, i.e. when applying the information, the program should not change semantics.

The iteration of the fixpoint algorithm will take the values in the direction of the maximum element. Initializing all blocks with the maximum element is therefore not useful. At least one block starts in a state with a value less than the maximum. The details depend on the

data-flow problem. If the minimum element represents totally conservative information, the results can be used safely even during the data-flow iteration. If it represents the most accurate information, fixpoint should be reached before the results can be applied.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>The following are examples of properties of computer programs that can be calculated by data-flow analysis.

Note that the properties calculated by data-flow analysis are typically only approximations of the real

properties. This is because data-flow analysis operates on the syntactical structure of the CFG without

simulating the exact control flow of the program.

However, to be still useful in practice, a data-flow analysis algorithm is typically designed to calculate

an upper respectively lower approximation of the real program properties.

</p>

<div class="mw-heading mw-heading3"><h3 id="Forward_analysis">Forward analysis</h3></div>

<p>The <a href="Reaching_definition" title="Reaching definition">reaching definition</a> analysis calculates for each program point the set of definitions that

may potentially reach this program point.

</p>

<div class="mw-highlight mw-highlight-lang-text mw-content-ltr mw-highlight-lines" dir="ltr"><pre> if b == 4 then

<span class="hll"> a = 5;

</span> else

<span class="hll"> a = 3;

</span> endif

<span class="hll"> if a < 4 then

</span> ...

</pre></div>

<p>The reaching definition of variable <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">a</code> at line 7 is the set of assignments <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">a = 5</code> at line 2 and <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">a = 3</code> at line 4.

</p>

<div class="mw-heading mw-heading3"><h3 id="Backward_analysis">Backward analysis</h3></div>

<p>The <a href="Live_variable_analysis" class="mw-redirect" title="Live variable analysis">live variable analysis</a> calculates for each program point the variables that may be

potentially read afterwards before their next write update. The result is typically used by

<a href="Dead_code_elimination" class="mw-redirect" title="Dead code elimination">dead code elimination</a> to remove statements that assign to a variable whose value is not used afterwards.

</p><p>The in-state of a block is the set of variables that are live at the start of it. It initially contains all variables live (contained) in the block, before the transfer function is applied and the actual contained values are computed. The transfer function of a statement is applied by killing the variables that are written within this block (remove them from the set of live variables). The out-state of a block is the set of variables that are live at the end of the block and is computed by the union of the block's successors' in-states.

</p><p>Initial code:

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .col-begin{border-collapse:collapse;padding:0;color:inherit;width:100%;border:0;margin:0}.mw-parser-output .col-begin-small{font-size:90%}.mw-parser-output .col-break{vertical-align:top;text-align:left}.mw-parser-output .col-break-2{width:50%}.mw-parser-output .col-break-3{width:33.3%}.mw-parser-output .col-break-4{width:25%}.mw-parser-output .col-break-5{width:20%}@media(max-width:720px){.mw-parser-output .col-begin,.mw-parser-output .col-begin>tbody,.mw-parser-output .col-begin>tbody>tr,.mw-parser-output .col-begin>tbody>tr>td{display:block!important;width:100%!important}.mw-parser-output .col-break{padding-left:0!important}}

/* end https://en.wikipedia.org/ */

</style><div>

<pre>b1: a = 3;

b = 5;

d = 4;

x = 100;

if a > b then

b2: c = a + b;

d = 2;

b3: endif

c = 4;

return b * d + c;

</pre>

<p>

</p>

</td></tr></tbody></table></div>

<p>Backward analysis:

</p>

<div>

<pre>// in: {}

b1: a = 3;

b = 5;

d = 4;

x = 100; //x is never being used later thus not in the out set {a,b,d}

if a > b then

// out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d}

// in: {a,b}

b2: c = a + b;

d = 2;

// out: {b,d}

// in: {b,d}

b3: endif

c = 4;

return b * d + c;

// out:{}

</pre>

<p>

</p>

</td></tr></tbody></table></div>

<p>The in-state of b3 only contains <i>b</i> and <i>d</i>, since <i>c</i> has been written. The out-state of b1 is the union of the in-states of b2 and b3. The definition of <i>c</i> in b2 can be removed, since <i>c</i> is not live immediately after the statement.

</p><p>Solving the data-flow equations starts with initializing all in-states and out-states to the empty set. The work list is initialized by inserting the exit point (b3) in the work list (typical for backward flow). Its computed in-state differs from the previous one, so its predecessors b1 and b2 are inserted and the process continues. The progress is summarized in the table below.

</p>

<th>processing

</th>

<th>out-state

</th>

<th>old in-state

</th>

<th>new in-state

</th>

<th>work list

</th></tr>

<tr>

<td>b3

</td>

<td>{}

</td>

<td>{}

</td>

<td>{b,d}

</td>

<td>(b1,b2)

</td></tr>

<tr>

<td>b1

</td>

<td>{b,d}

</td>

<td>{}

</td>

<td>{}

</td>

<td>(b2)

</td></tr>

<tr>

<td>b2

</td>

<td>{b,d}

</td>

<td>{}

</td>

<td>{a,b}

</td>

<td>(b1)

</td></tr>

<tr>

<td>b1

</td>

<td>{a,b,d}

</td>

<td>{}

</td>

<td>{}

</td>

<td>()

</td></tr></tbody></table>

<p>Note that b1 was entered in the list before b2, which forced processing b1 twice (b1 was re-entered as predecessor of b2). Inserting b2 before b1 would have allowed earlier completion.

</p><p>Initializing with the empty set is an optimistic initialization: all variables start out as dead. Note that the out-states cannot shrink from one iteration to the next, although the out-state can be smaller than the in-state. This can be seen from the fact that after the first iteration the out-state can only change by a change of the in-state. Since the in-state starts as the empty set, it can only grow in further iterations.

</p>

<div class="mw-heading mw-heading2"><h2 id="Other_approaches">Other approaches</h2></div>

<p>Several modern compilers use <a href="Static_single-assignment_form" title="Static single-assignment form">static single-assignment form</a> as the method for analysis of variable dependencies.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup>

</p><p>In 2002, Markus Mohnen described a new method of data-flow analysis that does not require the explicit construction of a data-flow graph,<sup id="cite_ref-Mohnen_2002_11-0" class="reference"><a href="#cite_note-Mohnen_2002-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> instead relying on <a href="Abstract_interpretation" title="Abstract interpretation">abstract interpretation</a> of the program and keeping a working set of program counters. At each conditional branch, both targets are added to the working set. Each path is followed for as many instructions as possible (until end of program or until it has looped with no changes), and then removed from the set and the next program counter retrieved.

</p><p>A combination of <a href="Control_flow_analysis" class="mw-redirect" title="Control flow analysis">control flow analysis</a> and data flow analysis has shown to be useful and complementary in identifying cohesive source code regions implementing functionalities of a system (e.g., <a href="Software_feature" title="Software feature">features</a>, <a href="Requirement" title="Requirement">requirements</a> or <a href="Use_case" title="Use case">use cases</a>).<sup id="cite_ref-Kuang_2015_12-0" class="reference"><a href="#cite_note-Kuang_2015-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Special_classes_of_problems">Special classes of problems</h2></div>

<p>There are a variety of special classes of dataflow problems which have efficient or general solutions.

</p>

<div class="mw-heading mw-heading3"><h3 id="Bit_vector_problems">Bit vector problems</h3></div>

<p>The examples above are problems in which the data-flow value is a set, e.g. the set of <a href="Reaching_definitions" class="mw-redirect" title="Reaching definitions">reaching definitions</a> (Using a bit for a definition position in the program), or the set of live variables. These sets can be represented efficiently as <b><a href="Bit_array" title="Bit array">bit vectors</a></b>, in which each bit represents set membership of one particular element. Using this representation, the join and transfer functions can be implemented as bitwise logical operations. The join operation is typically union or intersection, implemented by bitwise <i>logical or</i> and <i>logical and</i>.

The transfer function for each block can be decomposed in so-called <i>gen</i> and <i>kill</i> sets.

</p><p>As an example, in live-variable analysis, the join operation is union. The <i>kill</i> set is the set of variables that are written in a block, whereas the <i>gen</i> set is the set of variables that are read without being written first. The data-flow equations become

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}</annotation>

</semantics>

</math></span><img src="./767544c8a2a79e5bcced5aa47b06cd12699cc1f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:16.66ex; height:5.843ex;" alt="{\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}</annotation>

</semantics>

</math></span><img src="./538be6da7f357d58b053b22904c69d57a036e834.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.57ex; height:2.843ex;" alt="{\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}" loading="lazy"></span></dd></dl>

<p>In logical operations, this reads as

</p>

<pre>out(<i>b</i>) = 0

<b>for</b> <i>s</i> <b>in</b> succ(<i>b</i>)

out(<i>b</i>) = out(<i>b</i>) <b>or</b> in(<i>s</i>)

in(<i>b</i>) = (out(<i>b</i>) <b>and not</b> kill(<i>b</i>)) <b>or</b> gen(<i>b</i>)

</pre>

<p>Dataflow problems which have sets of data-flow values which can be represented as bit vectors are called <b>bit vector problems</b>, <b>gen-kill problems</b>, or <b>locally separable problems</b>.<sup id="cite_ref-Reps_1995_13-0" class="reference"><a href="#cite_note-Reps_1995-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> Such problems have generic polynomial-time solutions.<sup id="cite_ref-Knoop_1996_14-0" class="reference"><a href="#cite_note-Knoop_1996-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p><p>In addition to the reaching definitions and live variables problems mentioned above, the following problems are instances of bitvector problems:<sup id="cite_ref-Knoop_1996_14-1" class="reference"><a href="#cite_note-Knoop_1996-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Available_expression" title="Available expression">Available expressions</a></li>

<li>Very busy expressions</li>

<li><a href="Use-define_chain" title="Use-define chain">Use-definition chains</a></li></ul>

<div class="mw-heading mw-heading3"><h3 id="IFDS_problems">IFDS problems</h3></div>

<p><b>Interprocedural, finite, distributive, subset problems</b> or <b>IFDS</b> problems are another class of problem with a generic polynomial-time solution.<sup id="cite_ref-Reps_1995_13-1" class="reference"><a href="#cite_note-Reps_1995-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Naeem_2010_15-0" class="reference"><a href="#cite_note-Naeem_2010-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> Solutions to these problems provide context-sensitive and flow-sensitive dataflow analyses.

</p><p>There are several implementations of IFDS-based dataflow analyses for popular programming languages, e.g. in the Soot<sup id="cite_ref-Bodden_2012_16-0" class="reference"><a href="#cite_note-Bodden_2012-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> and WALA<sup id="cite_ref-Rapoport_2015_17-0" class="reference"><a href="#cite_note-Rapoport_2015-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> frameworks for Java analysis.

</p><p>Every bitvector problem is also an IFDS problem, but there are several significant IFDS problems that are not bitvector problems, including truly-live variables and possibly-uninitialized variables.

</p>

<div class="mw-heading mw-heading2"><h2 id="Sensitivities">Sensitivities</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Polyvariance" title="Polyvariance">Polyvariance</a></div>

<p>Data-flow analysis is typically path-insensitive, though it is possible to define data-flow equations that yield a path-sensitive analysis.

</p>

<ul><li>A <b>flow-sensitive</b> analysis takes into account the order of statements in a program. For example, a flow-insensitive pointer alias analysis may determine "variables <i>x</i> and <i>y</i> may refer to the same location", while a flow-sensitive analysis may determine "after statement 20, variables <i>x</i> and <i>y</i> may refer to the same location".</li>

<li>A <b>path-sensitive</b> analysis computes different pieces of analysis information dependent on the predicates at conditional branch instructions. For instance, if a branch contains a condition <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">x>0</code>, then on the <i>fall-through</i> path, the analysis would assume that <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">x<=0</code> and on the target of the branch it would assume that indeed <code class="mw-highlight mw-highlight-lang-text mw-content-ltr" style="" dir="ltr">x>0</code> holds.</li>

<li>A <b>context-sensitive</b> analysis is an <i>interprocedural</i> analysis that considers the calling context when analyzing the target of a function call. In particular, using context information one can <i>jump back</i> to the original call site, whereas without that information, the analysis information has to be propagated back to all possible call sites, potentially losing precision.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="List_of_data-flow_analyses">List of data-flow analyses</h2></div>

<ul><li><a href="Reaching_definitions" class="mw-redirect" title="Reaching definitions">Reaching definitions</a></li>

<li><a href="Liveness_analysis" class="mw-redirect" title="Liveness analysis">Liveness analysis</a></li>

<li><a href="Definite_assignment_analysis" title="Definite assignment analysis">Definite assignment analysis</a></li>

<li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Constant_propagation" class="mw-redirect" title="Constant propagation">Constant propagation</a></li></ul>

<ul><li><a href="Abstract_interpretation" title="Abstract interpretation">Abstract interpretation</a></li>

<li><a href="Control_flow_analysis" class="mw-redirect" title="Control flow analysis">Control flow analysis</a></li>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFKildall1972" class="citation book cs1"><a href="Gary_Arlen_Kildall" class="mw-redirect" title="Gary Arlen Kildall">Kildall, Gary Arlen</a> (May 1972). <i>Global expression optimization during compilation</i> (Ph.D. dissertation). Seattle, Washington, USA: <a href="University_of_Washington" title="University of Washington">University of Washington</a>, Computer Science Group. Thesis No. 20506, Technical Report No. 72-06-02.</cite></span>

</li>

<li id="cite_note-Kildall_1973_Optimization-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kildall_1973_Optimization_2-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKildall1973" class="citation book cs1"><a href="Gary_Kildall" title="Gary Kildall">Kildall, Gary Arlen</a> (1973-10-01). <a rel="nofollow" class="external text" href="http://static.aminer.org/pdf/PDF/000/546/451/a_unified_approach_to_global_program_optimization.pdf">"A unified approach to global program optimization"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73</i>. pp. <span class="nowrap">194–</span>206. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F512927.512945">10.1145/512927.512945</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10945%2F42162">10945/42162</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:10219496">10219496</a>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170629213307/http://static.aminer.org/pdf/PDF/000/546/451/a_unified_approach_to_global_program_optimization.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2017-06-29<span class="reference-accessdate">. Retrieved <span class="nowrap">2006-11-20</span></span>.</cite> (<a rel="nofollow" class="external autonumber" href="http://portal.acm.org/citation.cfm?id=512945&coll=portal&dl=ACM">[1]</a>)</span>

</li>

<li id="cite_note-Cortesi_1999-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cortesi_1999_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFRüthingKnoopSteffen2003" class="citation book cs1">Rüthing, Oliver; Knoop, Jens; <a href="Bernhard_Steffen_(computer_scientist)" title="Bernhard Steffen (computer scientist)">Steffen, Bernhard</a> (2003-07-31) [1999]. <a rel="nofollow" class="external text" href="https://books.google.com/books?id=ZwxqCQAAQBAJ&pg=PA233">"Optimization: Detecting Equalities of Variables, Combining Efficiency with Precision"</a>. In Cortesi, Agostino; Filé, Gilberto (eds.). <i>Static Analysis: 6th International Symposium, SAS'99, Venice, Italy, September 22–24, 1999, Proceedings</i>. Lecture Notes in Computer Science. Vol. 1694 (illustrated ed.). Springer. pp. 232–247 [233]. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540664598</bdi>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0302-9743">0302-9743</a>.</cite></span>

</li>

<li id="cite_note-Laws_2014_IEEE-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Laws_2014_IEEE_4-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFHuittEubanksRolanderLaws2014" class="citation web cs1">Huitt, Robert; <a href="Gordon_Eubanks" title="Gordon Eubanks">Eubanks, Gordon</a>; <a href="Thomas_Alan_Rolander" class="mw-redirect" title="Thomas Alan Rolander">Rolander, Thomas "Tom" Alan</a>; Laws, David; Michel, Howard E.; Halla, Brian; <a href="John_Harrison_Wharton" title="John Harrison Wharton">Wharton, John Harrison</a>; Berg, Brian; Su, Weilian; <a href="Scott_Kildall" title="Scott Kildall">Kildall, Scott</a>; Kampe, Bill (2014-04-25). Laws, David (ed.). <a rel="nofollow" class="external text" href="https://archive.computerhistory.org/resources/access/text/2014/06/102746909-05-01-acc.pdf">"Legacy of Gary Kildall: The CP/M IEEE Milestone Dedication"</a> <span class="cs1-format">(PDF)</span> (video transscription). Pacific Grove, California, USA: <a href="Computer_History_Museum" title="Computer History Museum">Computer History Museum</a>. CHM Reference number: X7170.2014<span class="reference-accessdate">. Retrieved <span class="nowrap">2020-01-19</span></span>. <q>[…] <a href="Gordon_Eubanks" title="Gordon Eubanks">Eubanks</a>: […] <a href="Gary_Arlen_Kildall" class="mw-redirect" title="Gary Arlen Kildall">Gary</a> […] was an inventor, he was inventive, he did things. His Ph.D. thesis proved that global flow analysis converges. […] This is a fundamental idea in computer science. […] I took a […] summer course once from a guy named Dhamdhere […] they talked about optimization for like a week and then they put a slide up and said, "Kildall's Method," this is the real story. […] that's something that no one ever thinks about. […]</q></cite> <a rel="nofollow" class="external autonumber" href="https://ethw.org/Milestones:The_CP/M_Microcomputer_Operating_System,_1974">[2]</a><a rel="nofollow" class="external autonumber" href="https://www.youtube.com/watch?v=HO6IPpL0y8g">[3]</a> (33 pages)</span>

</li>

<li id="cite_note-Kildall19732-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kildall19732_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKildall1973" class="citation book cs1">Kildall, Gary A. (1973). "A unified approach to global program optimization". <i>Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages - POPL '73</i>. pp. <span class="nowrap">194–</span>206. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F512927.512945">10.1145/512927.512945</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/10945%2F42162">10945/42162</a>.</cite></span>

</li>

<li id="cite_note-Aho2006-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-Aho2006_6-0">^</a></b></span> <span class="reference-text">Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006). Compilers: Principles, Techniques, and Tools (2nd ed.). Pearson. ISBN 978-0321486813.</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">Nielson, Flemming; Nielson, Hanne R.; Hankin, Chris (2005). Principles of Program Analysis. Springer. ISBN 978-3540654100.</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1558603202.</span>

</li>

<li id="cite_note-Cooper_2004-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cooper_2004_9-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFCooperHarveyKennedy2004" class="citation web cs1"><a href="Keith_D._Cooper" title="Keith D. Cooper">Cooper, Keith D.</a>; Harvey, Timothy J.; <a href="Ken_Kennedy_(computer_scientist)" title="Ken Kennedy (computer scientist)">Kennedy, Ken</a> (2004-03-26) [November 2002]. <a rel="nofollow" class="external text" href="https://www.cs.rice.edu/uploadedFiles/Computer_Science/Research/Tech_Reports/2004/TR04-432.pdf">"Iterative Data-Flow Analysis, Revisited"</a> <span class="cs1-format">(PDF)</span>. <i>PLDI 2003</i>. <a href="Association_for_Computing_Machinery" title="Association for Computing Machinery">ACM</a>. TR04-432<span class="reference-accessdate">. Retrieved <span class="nowrap">2017-07-01</span></span>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/static-single-assignment-with-relevant-examples/">"Static Single Assignment (with relevant examples)"</a>. <i>GeeksforGeeks</i>. 2021-10-02<span class="reference-accessdate">. Retrieved <span class="nowrap">2023-08-16</span></span>.</cite></span>

</li>

<li id="cite_note-Mohnen_2002-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-Mohnen_2002_11-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFMohnen2002" class="citation book cs1">Mohnen, Markus (2002). "A Graph—Free Approach to Data—Flow Analysis". <i>Compiler Construction</i>. Lecture Notes in Computer Science. Vol. 2304. pp. <span class="nowrap">185–</span>213. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45937-5_6">10.1007/3-540-45937-5_6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-43369-9</bdi>.</cite></span>

</li>

<li id="cite_note-Kuang_2015-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-Kuang_2015_12-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFKuangMäderHuGhabi2015" class="citation journal cs1">Kuang, Hongyu; Mäder, Patrick; Hu, Hao; Ghabi, Achraf; Huang, LiGuo; Lü, Jian; Egyed, Alexander (2015-11-01). "Can method data dependencies support the assessment of traceability between requirements and source code?". <i>Journal of Software: Evolution and Process</i>. <b>27</b> (11): <span class="nowrap">838–</span>866. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2Fsmr.1736">10.1002/smr.1736</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/2047-7481">2047-7481</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:39846438">39846438</a>.</cite></span>

</li>

<li id="cite_note-Reps_1995-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-Reps_1995_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Reps_1995_13-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFRepsHorwitzSagiv1995" class="citation book cs1">Reps, Thomas; Horwitz, Susan; Sagiv, Mooly (1995). "Precise interprocedural dataflow analysis via graph reachability". <i>Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '95</i>. New York, New York, USA: <a href="ACM_Press" class="mw-redirect" title="ACM Press">ACM Press</a>. pp. 1, <span class="nowrap">49–</span>61. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F199448.199462">10.1145/199448.199462</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791692-1</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:5955667">5955667</a>.</cite></span>

</li>

<li id="cite_note-Knoop_1996-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-Knoop_1996_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Knoop_1996_14-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFKnoopSteffenVollmer1996" class="citation journal cs1">Knoop, Jens; <a href="Bernhard_Steffen_(computer_scientist)" title="Bernhard Steffen (computer scientist)">Steffen, Bernhard</a>; Vollmer, Jürgen (1996-05-01). <a rel="nofollow" class="external text" href="https://publikationen.bibliothek.kit.edu/369596">"Parallelism for free: efficient and optimal bitvector analyses for parallel programs"</a>. <i>ACM Transactions on Programming Languages and Systems</i>. <b>18</b> (3): <span class="nowrap">268–</span>299. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F229542.229545">10.1145/229542.229545</a></span>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0164-0925">0164-0925</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:14123780">14123780</a>.</cite></span>

</li>

<li id="cite_note-Naeem_2010-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-Naeem_2010_15-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFNaeemLhotákRodriguez2010" class="citation cs2">Naeem, Nomair A.; Lhoták, Ondřej; Rodriguez, Jonathan (2010), "Practical Extensions to the IFDS Algorithm", <i>Compiler Construction</i>, Lecture Notes in Computer Science, vol. 6011, Berlin / Heidelberg, Germany: <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>, pp. <span class="nowrap">124–</span>144, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-11970-5_8">10.1007/978-3-642-11970-5_8</a></span>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-64211969-9</bdi></cite></span>

</li>

<li id="cite_note-Bodden_2012-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-Bodden_2012_16-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBodden2012" class="citation book cs1">Bodden, Eric (2012). "Inter-procedural data-flow analysis with IFDS/IDE and Soot". <i>Proceedings of the ACM SIGPLAN International Workshop on State of the Art in Java Program analysis</i>. New York, New York, USA: <a href="ACM_Press" class="mw-redirect" title="ACM Press">ACM Press</a>. pp. <span class="nowrap">3–</span>8. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2259051.2259052">10.1145/2259051.2259052</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-45031490-9</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:3020481">3020481</a>.</cite></span>

</li>

<li id="cite_note-Rapoport_2015-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-Rapoport_2015_17-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFRapoportLhotákTip2015" class="citation conference cs1">Rapoport, Marianna; Lhoták, Ondřej; Tip, Frank (2015). <i>Precise Data Flow Analysis in the Presence of Correlated Method Calls</i>. International Static Analysis Symposium. Lecture Notes in Computer Science. Vol. 9291. Berlin / Heidelberg, Germany: <a href="Springer_Verlag" class="mw-redirect" title="Springer Verlag">Springer Verlag</a>. pp. <span class="nowrap">54–</span>71. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-662-48288-9_4">10.1007/978-3-662-48288-9_4</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-66248287-2</bdi>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFCooperTorczon2003" class="citation book cs1"><a href="Keith_D._Cooper" title="Keith D. Cooper">Cooper, Keith D.</a>; Torczon, Linda (2003) [2002-01-01]. <i>Engineering a Compiler</i>. <a href="Morgan_Kaufmann" class="mw-redirect" title="Morgan Kaufmann">Morgan Kaufmann</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-698-2</bdi>.</cite></li>

<li><cite id="CITEREFMuchnick1997" class="citation book cs1"><a href="Steven_Stanley_Muchnick" class="mw-redirect" title="Steven Stanley Muchnick">Muchnick, Steven Stanley</a> (1997). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/advancedcompiler00much"><i>Advanced Compiler Design and Implementation</i></a></span>. <a href="Morgan_Kaufmann_Publishers" title="Morgan Kaufmann Publishers">Morgan Kaufmann Publishers</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-55860-320-2</bdi>.</cite></li>

<li><cite id="CITEREFHecht1977" class="citation book cs1">Hecht, Matthew S. (1977-05-03). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/flowanalysisofco0000hech"><i>Flow Analysis of Computer Programs</i></a></span>. Programming Languages Series. Vol. 5. <a href="Elsevier_North-Holland_Inc." class="mw-redirect" title="Elsevier North-Holland Inc.">Elsevier North-Holland Inc.</a> <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-44400210-5</bdi>.</cite></li>

<li><cite id="CITEREFKhedkerSanyalKarkare2009" class="citation book cs1">Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009). <a rel="nofollow" class="external text" href="http://www.cse.iitb.ac.in/~uday/dfaBook-web"><i>Data Flow Analysis: Theory and Practice</i></a>. <a href="CRC_Press" title="CRC Press">CRC Press</a> (<a href="Taylor_and_Francis_Group" class="mw-redirect" title="Taylor and Francis Group">Taylor and Francis Group</a>).</cite></li>

<li><cite id="CITEREFNielsonNielsonHankin2005" class="citation book cs1">Nielson, Flemming; <a href="Hanne_Riis_Nielson" title="Hanne Riis Nielson">Nielson, Hanne Riis</a>; Hankin, Chris (2005). <i>Principles of Program Analysis</i>. <a href="Springer_Science%2BBusiness_Media" title="Springer Science+Business Media">Springer Science+Business Media</a>.</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Compiler_optimizations253" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Compiler_optimizations253" style="font-size:114%;margin:0 4em"><a href="Optimizing_compiler" title="Optimizing compiler">Compiler optimizations</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Basic block</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Peephole_optimization" title="Peephole optimization">Peephole optimization</a></li>

<li><a href="Local_value_numbering" class="mw-redirect" title="Local value numbering">Local value numbering</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Loop_optimization" title="Loop optimization">Loop</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Automatic_vectorization" title="Automatic vectorization">Automatic vectorization</a></li>

<li><a href="Induction_variable" title="Induction variable">Induction variable</a></li>

<li><a href="Loop_fusion" class="mw-redirect" title="Loop fusion">Loop fusion</a></li>

<li><a href="Loop-invariant_code_motion" title="Loop-invariant code motion">Loop-invariant code motion</a></li>

<li><a href="Loop_inversion" title="Loop inversion">Loop inversion</a></li>

<li><a href="Loop_interchange" title="Loop interchange">Loop interchange</a></li>

<li><a href="Loop_nest_optimization" title="Loop nest optimization">Loop nest optimization</a></li>

<li><a href="Loop_splitting" title="Loop splitting">Loop splitting</a></li>

<li><a href="Loop_unrolling" title="Loop unrolling">Loop unrolling</a></li>

<li><a href="Loop_unswitching" title="Loop unswitching">Loop unswitching</a></li>

<li><a href="Software_pipelining" title="Software pipelining">Software pipelining</a></li>

<li><a href="Strength_reduction" title="Strength reduction">Strength reduction</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Available_expression" title="Available expression">Available expression</a></li>

<li><a href="Common_subexpression_elimination" title="Common subexpression elimination">Common subexpression elimination</a></li>

<li><a href="Constant_folding" title="Constant folding">Constant folding</a></li>

<li><a href="Dead_store" title="Dead store">Dead store</a> elimination</li>

<li><a href="Induction_variable_recognition_and_elimination" class="mw-redirect" title="Induction variable recognition and elimination">Induction variable recognition and elimination</a></li>

<li><a href="Live-variable_analysis" title="Live-variable analysis">Live-variable analysis</a></li>

<li><a href="Upwards_exposed_uses" title="Upwards exposed uses">Upwards exposed uses</a></li>

<li><a href="Use-define_chain" title="Use-define chain">Use-define chain</a></li>

<li><a href="Reaching_definition" title="Reaching definition">Reaching definitions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Static_single-assignment_form" title="Static single-assignment form">SSA</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Global_value_numbering" class="mw-redirect" title="Global value numbering">Global value numbering</a></li>

<li><a href="Sparse_conditional_constant_propagation" title="Sparse conditional constant propagation">Sparse conditional constant propagation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Code_generation_(compiler)" title="Code generation (compiler)">Code generation</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Instruction_scheduling" title="Instruction scheduling">Instruction scheduling</a></li>

<li><a href="Instruction_selection" title="Instruction selection">Instruction selection</a></li>

<li><a href="Register_allocation" title="Register allocation">Register allocation</a></li>

<li><a href="Rematerialization" title="Rematerialization">Rematerialization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Functional</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Deforestation_(computer_science)" title="Deforestation (computer science)">Deforestation</a></li>

<li><a href="Tail_call" title="Tail call">Tail-call elimination</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Global</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interprocedural_optimization" title="Interprocedural optimization">Interprocedural optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bounds-checking_elimination" title="Bounds-checking elimination">Bounds-checking elimination</a></li>

<li><a href="Compile-time_function_execution" title="Compile-time function execution">Compile-time function execution</a></li>

<li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Expression_templates" title="Expression templates">Expression templates</a></li>

<li><a href="Inline_expansion" title="Inline expansion">Inline expansion</a></li>

<li><a href="Jump_threading" title="Jump threading">Jump threading</a></li>

<li><a href="Partial_evaluation" title="Partial evaluation">Partial evaluation</a></li>

<li><a href="Profile-guided_optimization" title="Profile-guided optimization">Profile-guided optimization</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Static analysis</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alias_analysis" title="Alias analysis">Alias analysis</a></li>

<li><a href="Array-access_analysis" title="Array-access analysis">Array-access analysis</a></li>

<li><a href="Control-flow_analysis" title="Control-flow analysis">Control-flow analysis</a></li>

<li><a href="Dependence_analysis" title="Dependence analysis">Dependence analysis</a></li>

<li><a href="Escape_analysis" title="Escape analysis">Escape analysis</a></li>

<li><a href="Pointer_analysis" title="Pointer analysis">Pointer analysis</a></li>

<li><a href="Shape_analysis_(program_analysis)" title="Shape analysis (program analysis)">Shape analysis</a></li>

<li><a href="Value_range_analysis" title="Value range analysis">Value range analysis</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-06" href="https://en.wikipedia.org/wiki/?title=Data-flow_analysis&oldid=1294237439">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>